import java.util.HashMap;
import java.util.Map;

/**
 * 1. 两数之和
 * https://leetcode.cn/problems/two-sum/description/
 */
//老师写的hash
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap();
        for(int i = 0; i < nums.length; i++) {
            int x = target - nums[i];
            if(map.containsKey(x)) {
                return new int[]{i, map.get(x)};
            }
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }
}

//自己写的hash
// class Solution {
//     public int[] twoSum(int[] nums, int target) {
//         int n = nums.length;
//         int[] ret = new int[2];
//         Map<Integer, Integer> map = new HashMap();
//         for(int i = 1; i < n; i++) {
//             map.put(nums[i - 1], i - 1);
//             int tmp = target - nums[i];
//             if(map.containsKey(tmp)) {
//                 ret[0] = map.get(tmp);
//                 ret[1] = i;
//                 break;
//             }
//         }
//         return ret;
//     }
// }

//暴力
// class Solution {
//     public int[] twoSum(int[] nums, int target) {
//         int n = nums.length;
//         int[] ret = new int[2];
//         for(int i = n - 1; i >= 0; i--) {
//             for(int j = i - 1; j >= 0; j--) {
//                 if(nums[i] + nums[j] == target) {
//                     ret[0] = i; ret[1] = j;
//                     break;
//                 }
//             }
//         }
//         return ret;
//     }
// }